\section{Apresentação dos Resultados}
\label{avaliacao}

Nesta seção são apresentados os resultados obtidos nas duas fases de experimentação.

\subsection{Avaliação de estratégias e parâmetros}

Da primeira fase, foram obtidos resultados da execução de $1000$ experimentos para cada cenário da varredura de parâmetros, descritos na Seção \ref{metodologia}. Alguns parâmetros tiveram uma diferença significativa nos resultados ao variar seus valores. Os cenários com \textit{elitismo}, com \textit{cromossomos duplicados} e com \textit{geração da população inicial aleatória} tiveram um desempenho superior em todos os cenários executados. Portanto, esses valores foram fixados para os demais experimentos.

A Figura \ref{fig:comparacao-geracoes} compara cenários com relação à média do número de gerações necessárias para convergir para a melhor solução, mostrando o intervalo de confiança com confiabilidade de $95\%$. As estratégias estão ordenadas em ordem crescente de acordo com a média de gerações. Os cenários exibidos são das estratégias de torneio (\textit{Tournament}) com tamanhos ${1, 3 , 5, 7, 10}$ e probabilidades de seleção do melhor indivíduo ${0.9, 1}$, da estratégia de melhor \textit{fitness} (\textit{Best}) com probabilidade de seleção do melhor indivíduo ${0.7, 0.8, 0.9 e 1}$ e da estratégia de roleta baseada no custo (\textit{Weighted Roulette}).

\begin{figure}[htb]
\centering
 \includegraphics[scale=0.75]{images/geracoes.eps}
\caption{Média do número de gerações para convergir para a melhor solução, com intervalo de confiança para confiabilidade de $95\%$}
\label{fig:comparacao-geracoes}
\end{figure}

Verifica-se na Figura \ref{fig:comparacao-geracoes} que as $3$ melhores estratégias utilizam torneio como seletor natural, com probabilidade de escolha do melhor indivíduo de $0.9$. Elas variam apenas no tamanho do torneio, com os valores em ${5, 7, 10}$. Nesses $3$ cenários, a média de gerações foi menor que $2$. Porém, não podemos ainda concluir qual das estratégias obteve melhor desempenho, pois o intervalo de confiança da média do cenário com a melhor média (tamanho do torneio $10$) inclui a média dos outros dois cenários (tamanho dos torneios $5$ e $7$). Para escolher a melhor estratégia, utilizou-se como métrica o tempo necessário para convergência para a melhor solução. A comparação dos $3$ melhores cenários anteriores com relação ao tempo de convergência é apresentado na Figura \ref{fig:comparacao-tempo}, com o intervalo de confiança para confiabilidade de $95\%$.

\begin{figure}[htb]
\centering
 \includegraphics[scale=0.75]{images/tempo.eps}
\caption{Média do tempo necessário para convergir para a melhor solução, com intervalo de confiança para confiabilidade de $95\%$}
\label{fig:comparacao-tempo}
\end{figure}

Na Figura \ref{fig:comparacao-tempo}, observa-se que o cenário com tamanho de torneio $7$ obteve a melhor média do tempo de convergência para a melhor solução. Além disso, os intervalos de confiança não se interceptam. Podemos, com isso, ter indícios de que, com $95\%$ de confiabilidade, a melhor estratégia entre os cenários avaliados, de acordo com as nossas métricas, utiliza torneio de tamanho $7$ como seletor natural, com elitismo ativado, cromossomos duplicados permitidos, utiliza cadeia de inteiros para representar o cromossomo, geração da população inicial aleatória, tamanho da população inicial $512$, cruzamento heurístico (guloso 1), mutação com troca gulosa e taxa de mutação $5\%$.

\subsection{Avaliação de condições de parada}

É necessário encontrar valores adequados para a condição de parada híbrida adotada, que considera tanto um limite máximo de gerações quanto um limite de gerações sem que haja mudança no melhor \textit{fitness}. A Figura \ref{fig:cdf-geracoes} mostra a função distribuição acumulada (FDA) do número de gerações necessárias para que a melhor solução seja obtida, com $1000$ execuções da melhor estratégia escolhida na fase anterior. A Figura \ref{fig:cdf-repeticoes} mostra a função distribuição acumulada (FDA) do número máximo de repetições do melhor indivíduo até que se obtenha a melhor solução.

\begin{figure}[htb]
\centering
\subfigure[Função distribuição acumulada (FDA) do número de gerações necessárias para que a melhor solução seja obtida]{
 \includegraphics[scale=0.42]{images/cdf_geracoes.eps}
\label{fig:cdf-geracoes}
}
\subfigure[Função distribuição acumulada (FDA) do número máximo de repetições do melhor indivíduo até que se obtenha a melhor solução]{
\includegraphics[scale=0.42]{images/cdf_repeticoes.eps}
\label{fig:cdf-repeticoes}
}
\caption{Função de Distribuição Acumulada (FDA) para obtenção da melhor solução}
\end{figure}

Com essas duas distribuições, podemos escolher valores para os dois parâmetros da condição de parada híbrida, com uma certa probabilidade da melhor solução ser encontrada. Por exemplo, com o limite máximo de gerações igual a 10, podemos ver na Figura \ref{fig:cdf-geracoes} que a melhor solução é obtida quase $100\%$ das vezes. Na Figura \ref{fig:cdf-repeticoes}, podemos obter, por exemplo, o 0.98-quantil, e verificar que em aproximadamente $98\%$ das vezes a melhor solução é obtida com apenas $2$ repetições do melhor indivíduo de uma geração até que a melhor solução seja encontrada. A escolha desses valores depende muito do risco que se quer ter na probabilidade de obter a solução ótima. Um possível valor para os parâmetros são esses exemplificados, que possuem uma baixa probabilidade da solução ótima não ser encontrada.

\section{Análise dos Resultados}

Os resultados mostram a avaliação de uma vasta gama de estratégias e parâmetros para resolver o PCV descrito no estudo de caso. Considerando a quantidade de experimentos feitos e as análises estatísticas, os resultados dão boas evidência sobre o melhor desempenho de algumas estratégias com relação a outras, apresentando boas soluções para o problema. 

Porém, apesar da grande quantidade de cenários avaliados, não se pode concluir que a solução escolhida é a melhor existente, pois muitos outros parâmetros que não foram considerados na análise podem influenciar o desempenho, além de outros possíveis valores dos parâmetros considerados. Uma avaliação mais completa tornou-se inviável para o escopo do projeto pela explosão de cenários que iria gerar. Além disso, a avaliação foi baseada em apenas um estudo de caso. Não podemos concluir que as estratégias se comportarão da mesma forma para outras instâncias do PCV, ou para outros problemas que possam fazer uso de AG.